class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int> > Print(TreeNode* pRoot) {
        levelOrder(pRoot);
        return results;
    }

    void levelOrder(TreeNode* root)
    {
        if(root == nullptr)
            return;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            int oldSize = q.size();
            vector<int> tmp;
            while(oldSize--)
            {
                TreeNode* node = q.front();
                tmp.push_back(node->val);
                q.pop();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }

            results.push_back(tmp);
        }

        for(int i = 0; i < results.size(); ++i)
        {
            if(i % 2)
            {
                reverse(results[i].begin(), results[i].end());
            }
        }
    }
};


// class Solution {
// public:
//     unordered_map<int, int> inMap;
//     TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& inOrder) {
//         for(int i = 0; i < inOrder.size(); ++i)
//         {
//             inMap[inOrder[i]] = i;
//         }

//         return buildTree(preOrder, 0, preOrder.size()-1, inOrder, 0, inOrder.size()-1);
//     }

//     TreeNode* buildTree(vector<int>& preOrder, int preStart, int preEnd, vector<int>& inOrder, int inStart, int inEnd)
//     {
//         if(preStart > preEnd || inStart > inEnd)
//             return nullptr;
        
//         TreeNode* rootNode = new TreeNode(preOrder[preStart]);
//         int rootNodeIndex = inMap[rootNode->val];
//         int subLeftLen = rootNodeIndex - inStart;

//         rootNode->left = buildTree(preOrder, preStart+1, preStart+subLeftLen, inOrder, inStart, rootNodeIndex-1);
//         rootNode->right = buildTree(preOrder, preStart+subLeftLen+1, preEnd, inOrder, rootNodeIndex+1, inEnd);

//         return rootNode;
//     }
// };



class Solution {
public:
    unordered_map<int,int> inOrderMap;
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& inOrder) {
        for(int i = 0; i < inOrder.size(); ++i)
            inOrderMap[inOrder[i]] = i;

        TreeNode* ret = buildTree(preOrder, 0, preOrder.size()-1, inOrder, 0, inOrder.size()-1);

        return ret;
    }

    TreeNode* buildTree(vector<int>& preOrder, int preStart, int preEnd, vector<int>& inOrder, int inStart, int inEnd)
    {
        if(preStart > preEnd || inStart > inEnd)
        {
            return nullptr;
        }

        auto* root = new TreeNode(preOrder[preStart]);
        int rootIndex = inOrderMap[root->val];
        int subLeftLen = rootIndex - inStart;

        root->left = buildTree(preOrder, preStart+1, preStart+subLeftLen, inOrder, inStart, rootIndex-1);
        root->right = buildTree(preOrder, preStart+subLeftLen+1, preEnd, inOrder, rootIndex+1, inEnd);

        return root;
    }
};


